翻訳と辞書 Words near each other ・ Cartesian closed category ・ Cartesian coordinate robot ・ Cartesian coordinate system ・ Cartesian diver ・ Cartesian doubt ・ Cartesian Dreams ・ Cartesian linguistics ・ Cartesian materialism ・ Cartesian Meditations ・ Cartesian monoid ・ Cartesian monoidal category ・ Cartesian Other ・ Cartesian oval ・ Cartesian Perceptual Compression ・ Cartesian product ・ Cartesian product of graphs ・ Cartesian Reflections ・ Cartesian Self ・ Cartesian skyscraper ・ Cartesian tensor ・ Cartesian theater ・ Cartesian tree ・ Cartesianism ・ Cartesio Oktató és Szolgáltató bt ・ Cartha DeLoach ・ Cartha Doyle ・ Cartha Queens Park RFC ・ Carthade ・ Carthage ・ Carthage (disambiguation) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Cartesian product of graphs ： ウィキペディア英語版 Cartesian product of graphs In graph theory, the Cartesian product ''G'' $\backslash square$ ''H'' of graphs ''G'' and ''H'' is a graph such that * the vertex set of ''G'' $\backslash square$ ''H'' is the Cartesian product ''V(G)'' × ''V(H)''; and * any two vertices ''(u,u')'' and ''(v,v')'' are adjacent in ''G'' $\backslash square$ ''H'' if and only if either * * ''u'' = ''v'' and ''u' '' is adjacent with ''v' '' in ''H'', or * * ''u' '' = ''v' '' and ''u'' is adjacent with ''v'' in ''G''. Cartesian product graphs can be recognized efficiently, in linear time.〔. For earlier polynomial time algorithms see and .〕 The operation is commutative as an operation on isomorphism classes of graphs, and more strongly the graphs ''G'' $\backslash square$ ''H'' and ''H'' $\backslash square$ ''G'' are naturally isomorphic, but it is not commutative as an operation on labeled graphs. The operation is also associative, as the graphs (''F'' $\backslash square$ ''G'') $\backslash square$ ''H'' and ''F'' $\backslash square$ (''G'' $\backslash square$ ''H'') are naturally isomorphic. The notation ''G'' × ''H'' is occasionally also used for Cartesian products of graphs, but is more commonly used for another construction known as the tensor product of graphs. The square symbol is the more common and unambiguous notation for the Cartesian product of graphs. It shows visually the four edges resulting from the Cartesian product of two edges. ==Examples== * The Cartesian product of two edges is a cycle on four vertices: K2 $\backslash square$ K2 = C4. * The Cartesian product of K2 and a path graph is a ladder graph. * The Cartesian product of two path graphs is a grid graph. * The Cartesian product of ''n'' edges is a hypercube: :: $(K\_2)^\; =\; Q\_n.$ :Thus, the Cartesian product of two hypercube graphs is another hypercube: Qi $\backslash square$ Qj = Qi+j. * The Cartesian product of two median graphs is another median graph. * The graph of vertices and edges of an n-prism is the Cartesian product graph K2 $\backslash square$ Cn. * The rook's graph is the Cartesian product of two complete graphs. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cartesian product of graphs」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.